\section{Model and problem statement}
\label{sec:pre}
In this section, we formally define the $k$-gossip problem, the online
and offline models, and token-forwarding algorithms.  

\smallskip
{\noindent {\sl The $k$-gossip problem.}} In this problem, $k$
different tokens are assigned to a set $V$ of $n \ge k$ nodes, where
each node may have any subset of the tokens, and the goal is to
disseminate all the $k$ tokens to all the nodes.

\smallskip
{\noindent {\sl The online model.}}  Our online model is the
worst-case adversarial model of~\cite{kuhn+lo:dynamic}.  Nodes
communicate with each other using anonymous broadcast.  We assume a
synchronized communication.  At the beginning of round $r$, each node
in $V$ decides what message to broadcast based on its internal state
and coin tosses (for a randomized algorithm); the adversary chooses
the set of edges that forms the communication network $G_r$ over $V$
for round $r$.  We adopt a {\em strong adversary}\/ model in which
adversary knows the outcomes of the random coin tosses used by the
algorithm in round $r$ at the time of constructing $G_r$ but is
unaware at this time of the outcomes of any randomness used by the
algorithm in future rounds.  The only constraint on $G_r$ is that it
be connected; this is the same as the $1$-interval connectivity model
of~\cite{kuhn+lo:dynamic}.  

As observed in~\cite{kuhn+lo:dynamic}, the above model is equivalent
to the adversary knowing the messages to be sent in round $r$ before
choosing the edges for round $r$.  We do not place any bound on the
size of the messages, but require for our lower bound that each
message contains at most one token.  Finally, we note that under the
strong adversary model, there is a distinction between randomized
algorithms and deterministic algorithms since a randomized algorithm
may be able to exploit the fact that in any round $r$, while the
adversary is aware of the randomness used in that round, it does not
know the outcomes of any randomness used in subsequent rounds.

\smallskip
{\noindent {\sl The offline model.}} In the offline model, we are
given a sequence of networks $\langle G_r \rangle$ where $G_r$ is a
connected communication network for round $r$.  As in the online
model, we assume that in each round at most one token is broadcast by
any node.  It can be easily seen that the $k$-gossip problem can be
solved in $nk$ rounds in the offline model; so we may assume that the
given sequence of networks is of length at most $nk$.

\smallskip
{\noindent {\sl Token-forwarding algorithms.}} Informally, a
token-forwarding algorithm is one that does not combine or alter
tokens, only stores and forwards them.  Formally, we call an algorithm
for $k$-gossip a token-forwarding algorithm if for every node $v$,
token $t$, and round $r$, $v$ contains $t$ at the start of round $r$
of the algorithm if and only if either $v$ has $t$ at the start of the
algorithm or $v$ received a message containing $t$ prior to round $r$.

Finally, several of our arguments are probabilistic.  We use the term
``with high probability'' to mean with probability at least $1 -
1/n^c$, for a constant $c$ that can be made sufficiently high by
adjusting related constant parameters.

\junk{
\begin{problem}[$k$-token dissemination]
\label{prob:ktoken}
\end{problem}

We assume synchronized communication between nodes, and the message
size is $O(\log n)$ where $n$ is the number of nodes in the graph. The
dynamic graphs are provided by adversaries. We consider the following
3 kinds of adversaries.
\begin{enumerate}
\item {\sc Strong Adversary}: At each round of communication, each
  node decides which token to send first. The adversary knows which
  node is going to send which token and the set of tokens each node
  has, and then the adversary provides a connected graph as the
  communication graph.
\item {\sc Weak Adversary}: At each round of communication, the
  adversary provides a connected graph as the communication graph
  first. Each node knows who are his neighbors, and then decides which
  token to send. The adversary knows the set of tokens each node has
  at any time.
\item {\sc Oblivious Adversary}: Before the token dissemination
  process starts, the adversary has to provide a sequence of graphs
  for all rounds of communications. 
\end{enumerate}
}
